package leetcode.D800.T743;

import java.util.*;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-19 17:39:56 星期六
 */

class Solution {

    static class Node {
        int dst;
        int dist;

        public Node(int dst, int dist) {
            this.dst = dst;
            this.dist = dist;
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        List<Node>[] graph = new List[n+1];
        buildGraph(times, graph);
        return dijstra(graph, n, k);
    }

    private void buildGraph(int[][] times, List<Node>[] graph) {
        for (int i = 1; i < graph.length; i++)
            graph[i] = new ArrayList<>();
        for (int i=0; i<times.length; ++i)
            graph[times[i][0]].add(new Node(times[i][1], times[i][2]));
    }

    private int dijstra(List<Node>[] graph, int n, int k) {
        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Set<Integer> vset = new HashSet<>();
        dist[k] = 0;
        for (int i=0; i<n; ++i) {
            int t = -1, minDist = Integer.MAX_VALUE;
            for (int j=1; j<=n; ++j) {
                if (!vset.contains(j) && dist[j] < minDist) {
                    t = j;
                    minDist = dist[j];
                }
            }
            if (t < 0)
                break;
            vset.add(t);
            for (Node node : graph[t]) {
                dist[node.dst] = Math.min(dist[node.dst], dist[t]+node.dist);
            }
        }
        if (vset.size() < n)
            return -1;
        else {
            int maxDist = 0;
            for (int i = 1; i <= n; i++)
                maxDist = Math.max(maxDist, dist[i]);
            return maxDist;
        }
    }
}